9033. Жадный Азиз

 

Знаете ли Вы, что Азиз очень любит шоколадные конфеты? Однако отец не позволяет ему есть много шоколада, так как он вредит зубам.

Отец дал ему массив, в котором много одинаковых чисел. В день Азиз может сьесть столько конфет, сколько раз повторяется максимально встречаемое число в массиве.

Азиз хочет смошенничать чтобы съесть больше конфет. Он может изменить некоторые числа в массиве, и отец этого не заметит. Он может увеличить или уменьшить любое число в массиве на 1 единицу и только 1 раз.

Азиз хочет съесть максимальное количество конфет. Помогите ему в этом деле.

Найдите максимальное количество конфет, которое Азиз может получить.

 

Вход. Первая строка содержит количество элементов n (1 ≤ n ≤ 105) в массиве. Вторая строка содержит n элементов ai (0 ≤ ai ≤ 109) массива.

 

Выход. Выведите максимальное количество конфет, которое Азиз может получить.

 

Пример входа 1

Пример выхода 1

2

1 2

2

 

 

Пример входа 2

Пример выхода 2

4

1 3 3 5

3

 

 

РЕШЕНИЕ

структура данных map

 

Анализ алгоритма

Подсчитаем количество раз, которое каждое число встречается в массиве. Для этого воспользуемя структурой данных map: m[x] будет содержать количество раз, которое число x встречается в массиве.

Для каждого числа a[i] в массиве предположим что оно является максимально встречаемым после мошенничества Азиза. Для этого Азиз должен число (a[i] – 1) увеличить на 1, а число (a[i] + 1) уменьшить на 1 (если такие числа в массиве существуют). Например пусть массив имеет вид

Структура map содержит следующие данные (две пятерки, две шестерки и четыре семерки):

m[5] = 2, m[6] = 2, m[7] = 4

Для того чтобы число 6 было максимально встречаемым после мошенничества, необходимо ко всем числам 5 прибавить 1, а изо всех чисел 7 вычесть 1:

Пусть изначально a[i] = 6. Тогда массив изначально содержит m[a[i]] шестерок, m[a[i] – 1] пятерок и m[a[i] + 1] семерок. После мошенничества число шестерок станет равным

m[a[i] – 1] + m[a[i]] + m[a[i] + 1],

что и будет равно количеству полученных Азизом конфет.

 

Рассмотрим ситуацию когда массив содержит два числа a[i] = 4 и a[i] + 2 = 6 (разность между которыми равна 2), но при этом число a[i] + 1 например может отсутствовать.

В таком случае оптимально будет все числа a[i] увеличить на 1, а все числа a[i] + 2 уменьшить на 1. После мошенничества количество чисел a[i] + 1 станет равным

m[a[i]] + m[a[i] + 1] + m[a[i] + 2]

 

Реализация алгоритма

Объявим входной массив a. Объявим переменную m типа map.

 

map<int, int> m;

int a[100000];

 

Читаем входной массив. Подсчитаем количество раз, которое каждое число a[i] встречается в массиве a.

 

scanf("%d", &n);

for (i = 0; i < n; i++)

{

  scanf("%d", &a[i]);

  m[a[i]]++;

}

 

В переменной res вычисляем ответ.

 

int res = 0;

for (int i = 0; i < n; i++)

{

 

Если максимально встречаемым числом после мошеничества будет a[i].

 

  res = max(res, m[a[i]] + m[a[i] - 1] + m[a[i] + 1]);

 

Если максимально встречаемым числом после мошеничества будет a[i] + 1.

 

  res = max(res, m[a[i]] + m[a[i] + 1] + m[a[i] + 2]);

}

 

Выводим ответ.

 

printf("%d\n", res);

 

Java реализация

 

import java.util.*;

 

public class Main

{

  static Map<Integer, Integer> m = new HashMap<Integer, Integer>();

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    int a[] = new int[n];

    for (int i = 0; i < n; i++)

    {

      a[i] = con.nextInt();

      if (!m.containsKey(a[i]))

        m.put(a[i], 1);

      else

        m.put(a[i], m.get(a[i]) + 1);

    }

  

    int res = 0;

    for (int i = 0; i < n; i++)

    {

      int ai = 0;

      if (m.containsKey(a[i])) ai = m.get(a[i]);

      int aim1 = 0;

      if (m.containsKey(a[i]-1)) aim1 = m.get(a[i]-1);

      int aip1 = 0;

      if (m.containsKey(a[i]+1)) aip1 = m.get(a[i]+1);

      int aip2 = 0;

      if (m.containsKey(a[i]+2)) aip2 = m.get(a[i]+2);     

     

      res = Math.max(res, ai + aim1 + aip1);

      res = Math.max(res, ai + aip1 + aip2);

    }

   

    System.out.println(res);

    con.close();

  }

}